package com.mlh.dp.old;

// 给你一个整数数组 nums，返回 nums 中最长等差子序列的长度。
// 回想一下，nums 的子序列是一个列表 nums[i1], nums[i2], ..., nums[ik] ，且 0 <= i1 < i2 < ... < ik <= nums.length - 1。
// 并且如果 seq[i+1] - seq[i]( 0 <= i < seq.length - 1) 的值都相同，那么序列 seq 是等差的。

// 输入：nums = [9,4,7,2,10]
// 输出：3
// 解释：
// 最长的等差子序列是 [4,7,10]。

import java.util.Arrays;

public class LongestArithSeqLength {

    public static void main(String[] args) {
        int[]nums={22,8,57,41,36,46,42,28,42,14,9,43,27,51,0,0,38,50,31,60,29,31,20,23,37,53,27,1,47,42,28,31,10,35,39,12,15,6,35,31,45,21,30,19,5,5,4,18,38,51,10,7,20,38,28,53,15,55,60,56,43,48,34,53,54,55,14,9,56,52};
        method1(nums);
    }

    //思路还是和之前差不多
    //不过dp数组变成二维的  第二维 是差值
    //简单来说就是 dp[i][d] 表示前i个nums 组成等差数列差值为d 的最长长度
    //对i之前的数全部计算差值   利用dp数组来看看在某个差值上有没有更长的等差数列
    //本质是记忆搜索
    public static int method1(int[] nums){
        int[][]dp=new int[nums.length][1001];
        int res=0;
        if(nums.length<2){
            return 0;
        }
        for(int i=1;i<nums.length;i++){
            for(int j=i-1;j>=0;j--){
                int k=nums[i]-nums[j]+500;
                if(dp[i][k]==0){
                    dp[i][k]=2;
                }
                if(dp[i][k]<dp[j][k]+1){
                    dp[i][k]=dp[j][k]+1;
                }
                res=Math.max(res,dp[i][nums[i]-nums[j]+500]);
            }
        }
        // 打印二维数组
        // System.out.println(Arrays.deepToString(dp));
        return res;
    }
}
